package com.chj.jz.dp.class04;

public class Code06_BackpackV {
	/**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public static int backPackV(int[] nums, int target) {
        // write your code here
    	int n = nums.length;
    	int[] f = new int[target + 1];
    	int i, j;
    	
    	f[0] = 1;
    	for(i = 1; i <= target; i++) {
    		f[i] = 0;
    	}
    	
    	for(i = 1; i <= n; i++) {
    		for(j = target; j >= 0; j--) {
    			if(j >= nums[i - 1]) {
    				f[j] += f[j - nums[i - 1]];
    			}
    		}
    	}
    	
    	return f[target];
    }
    
    public static void main(String[] args) {
		{
			int[] arr = new int[] {1, 2, 3, 3, 7};
			int k = 7;
			System.out.println(backPackV(arr, k));
		}
		{
//			int[] arr = new int[] {2, 3, 5, 7};
//			int k = 12;
//			System.out.println(backPackV(k, arr));
		}
    }

}
